package algorithm.middle;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: SearchMatrix74
 * @description: 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 *
 *     每行中的整数从左到右按升序排列。
 *     每行的第一个整数大于前一行的最后一个整数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 * 输出：true
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-a-2d-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/3/3010:26
 * @since V1.0
 */
//二维矩阵
public class SearchMatrix74 {
    public static void main(String[] args) {
        searchMatrix(new int[][]{{1}},2);
    }

    //二分法 O(logm + logn)
    public static boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix[0].length;
        //二分查找行
        int left = 0;
        int right = matrix.length-1;
        int mid=0;
        while (true){
            mid = (left+right)/2;
            if (target>=matrix[mid][0] && target<=matrix[mid][n-1]){
                break;
            }else if (target<matrix[mid][0]){
                right = mid-1;
            }else if (target>=matrix[mid][n-1]){
                left = mid+1;
            }
            if (left>right){
                return false;
            }
        }
        //此处也能二分，懒得写了
        for (int i=0;i<n;i++){
            if (matrix[mid][i]==target){
                return true;
            }
        }
        return false;
    }

    //O(m+n) 二维矩阵 从右上角开始找 下左方向
    public boolean fun(int[][] matrix, int target) {
        for (int i=0;i<matrix.length;i++){
            if (target<=matrix[i][matrix[0].length-1]){
                for (int j=matrix[0].length-1;j>=0;j--){
                    if (matrix[i][j]==target){
                        return true;
                    }
                }
            }

        }
        return false;
    }
}
